package com.wzq.solution;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution51 {

    private int n;
    private List<Character[]> nn;
    private List<List<String>> rst = new ArrayList<List<String>>();
    private int[] queenPos;


    public List<List<String>> solveNQueens(int n) {
        init(n);
        queen(0);
        return rst;
    }

    private void init(int n){
        this.n = n;


        nn = new ArrayList<Character[]>(n);
        Character[] ca = new Character[n];
        for (int i=0;i<n;i++){
            ca[i] = '.';
        }
        for (int i=0;i<n;i++){
            nn.add(Arrays.copyOf(ca,n));
        }

        queenPos = new int[n];
    }

    private void queen(int row){
        if(row == n){

            List<String> t = new ArrayList<String>();

            for (int i=0;i<n;i++){
                StringBuilder sb = new StringBuilder();
                for (int j=0;j<n;j++){
                    sb.append(nn.get(i)[j]);
                }

                t.add(sb.toString());
            }
            rst.add(t);

        }else{
            for (int j=0;j<n;j++){
                if(check(row,j)){
                    nn.get(row)[j] = 'Q';
                    queenPos[row] = j;

                    queen(row+1);

                    nn.get(row)[j] = '.';

                }
            }
        }
    }

    private boolean check(int i,int j){
        for (int x=0;x<i;x++){
            int y = queenPos[x];

            if(y==j || (i-x == j-y) || (i+j == x+y)){
                return false;
            }
        }
        return true;
    }


    public static void main(String[] args) {
        System.out.println(new Solution51().solveNQueens(4));
    }

}